Crate trees[−][src]

trees

General purpose tree library.

The current version provides the tree implemented in classic child-sibling nodes. More kinds of trees may be added in the future.

This crate can be used with or without libstd.

Quick start

Tree notation

use trees::tr;      // tr stands for tree
tr(0);              // A single tree node with data 0. tr(0) has no children
tr(0) /tr(1);       // tr(0) has one child tr(1)
tr(0) /tr(1)/tr(2); // tr(0) has children tr(1) and tr(2)
 
// tr(0) has children tr(1) and tr(4), while tr(1) has children tr(2) and tr(3), and tr(4) has children tr(5) and tr(6).
// The spaces and carriage returns are for pretty format and do not make sense.
tr(0)
    /( tr(1) /tr(2)/tr(3) )
    /( tr(4) /tr(5)/tr(6) );

Forest notation

use trees::{tr,fr}; // fr stands for forest

fr::<i32>();        // An empty forest
fr() - tr(1);       // forest has one child tr(1)
- tr(1);            // forest has one child tr(1). The fr() can be omitted. The Neg operator for Tree converts the tree to a forest.
- tr(1) - tr(2);    // forest has child tr(1) and tr(2)
tr(1) - tr(2);      // forest has child tr(1) and tr(2). The leading neg can be omitted.
 
// forest has children tr(1) and tr(4), while tr(1) has children tr(2) and tr(3), and tr(4) has children tr(5) and tr(6).
-( tr(1) /tr(2)/tr(3) )
-( tr(4) /tr(5)/tr(6) );

// A tree tr(0) whose children equal to the forest descripted above.
tr(0) /(
    -( tr(1) /( -tr(2)-tr(3) ) )
    -( tr(4) /( -tr(5)-tr(6) ) )
);

Tree traversal, using Node::children() recursively

use std::string::{String,ToString};
use trees::{tr,Node};

let tree = tr(0)
    /( tr(1) /tr(2)/tr(3) )
    /( tr(4) /tr(5)/tr(6) );

fn tree_to_string<T:ToString>( node: &Node<T> ) -> String {
    if node.is_leaf() {
        node.data.to_string()
    } else {
        node.data.to_string()
            + &"( "
            + &node.children()
                .fold( String::new(),
                    |s,c| s + &tree_to_string(c) + &" " )
            + &")"
    }
}

assert_eq!( tree_to_string( &tree ), "0( 1( 2 3 ) 4( 5 6 ) )" );

String representation

The Debug and Display trait has been implemented that is essentially the same as tree_to_tring() mentioned above.

Children are seperated by spaces and grouped in the parentheses that follow their parent closely.

use trees::{tr,fr};

let tree = tr(0) /( tr(1) /tr(2)/tr(3) ) /( tr(4) /tr(5)/tr(6) );
let str_repr = "0( 1( 2 3 ) 4( 5 6 ) )";
assert_eq!( tree.to_string(), str_repr );
assert_eq!( format!( "{:?}", tree ), str_repr );
 
assert_eq!( fr::<i32>().to_string(), "()" );
 
let forest = -( tr(1) /tr(2)/tr(3) ) -( tr(4) /tr(5)/tr(6) );
let str_repr = "( 1( 2 3 ) 4( 5 6 ) )";
assert_eq!( forest.to_string(), str_repr );
assert_eq!( format!( "{:?}", fr::<i32>() ), "()" );

Slow start

Concepts

Tree is composed of a root Node and an optional Forest as its children. A tree can NOT be empty.

use trees::{tr,Tree,Forest};

let mut tree: Tree<i32> = tr(0);
let forest: Forest<i32> = -tr(1)-tr(2)-tr(3);
tree.append( forest );
let forest = tree.abandon();

Forest is composed of Nodes as its children. A forest can be empty.

use trees::{tr,fr,Tree,Forest};

let mut forest: Forest<i32> = fr(); // an empty forest
forest.push_back( tr(1) );          // forest has one tree
forest.push_back( tr(2) );          // forest has two trees

Node is a borrowed tree, and Tree is an owned Node. All nodes in a tree can be referenced as &Node, but only the root node can be observed as Tree by the user.

use trees::{tr,Tree,Node};
use std::borrow::Borrow;

let mut tree: Tree<i32>  = tr(0) /tr(1)/tr(2)/tr(3);
{
    let root: &Node<i32> = tree.borrow(); // you can also use tree.root()
    let first_child : &Node<i32> = tree.children().next().unwrap();
    let second_child: &Node<i32> = tree.children().nth(1).unwrap();
    let third_child : &Node<i32> = tree.children().last().unwrap();
}
let first_child: Tree<i32> = tree.pop_front().unwrap();

Iterators

The children nodes of a node, or a forest, is conceptually a forward list.

Using children() to iterate over referenced child Nodes, you can:

1.1 read the data associated with each node.

1.2 use children() to iterate over children's children, etc.
Using children_mut() to iterate over referenced child Nodes, you can:

2.1 read/write the data associated with each node, or prepend(), append, abandon(), push_front(), pop_front(), push_back() child node(s) in constant time.

2.2 use children_mut() to iterate over children's children, etc.
Using subtrees() to iterate over Subtrees, you can:

3.1 insert_before, insert_after(), depart() node(s) at any position.

3.2 do whatever children() or children_mut() can do.
Using Forest::<T>::into_iter() to iterate over Trees, you can:

do whatever you want to.

Traversal

Using TreeWalk/ForestWalk to traverse on Tree/Forest, you can:

read the data associated with each descendant node in depth first manner, preorder or postorder at will.
visit Nodes irregularly, unlike the iterators mentioned above that are usually called intensively.

Resource management

Tree/Forest will recursively destruct all the nodes owned by them when reaching the end of their lifetimes.
Clone for Tree and Forest makes deep copy which clones all its decendant nodes. To do copy for just one node, simplely let cloned = trees::tr( node.data.clone() );.
No bookkeeping of size information.

Panics

No panics unless Clone is involved:

Node::<T>::to_owned()
Tree::<T>::clone()
Forest::<T>::clone()
all of the operator overloading functions the operands of which contain at least one referenced type.

Panics if and only if T::clone() panics.

Re-exports

pub use sib::Visit;

pub use sib::TreeWalk;

pub use sib::ForestWalk;

Modules

sib	`Tree`/`Forest` implemented in last-child/next-sibling `Node`s, allocated on heap

Structs

Forest	A nullable forest
Iter	An iterator over the sub `Node`s of a `Node` or `Forest`.
IterMut	A mutable iterator over the sub `Node`s of a `Node` or `Forest`.
Node
Subtree	Wrapper of `Node` for allowing modification of parent or sib links. Any `Node` that is the root of some `Tree` is impossible to be `Subtree`.
SubtreeIter	Mutable iterator allowing modification of parent or sib links.
Tree	A non-nullable tree

Functions

fr
tr